This paper describes some representations of a mapping and their simplification. Any mapping from a finite set into another can be represented by a sequence of Boolean functinos if we encode its domain and range to finite binary sequences. The complexity of the representation depends on the encoding. We present a problem of finding an algorithm that derives one of the simplest representations of a given mapping, and solve it in a case where the complexity measure is determined according to the number of literals in disjunctive forms.
Masayuki KANDA Shiho MORIAI Kazumaro AOKI Hiroki UEDA Youichi TAKASHIMA Kazuo OHTA Tsutomu MATSUMOTO
This paper describes the design principles, the specification, and evaluations of a new 128-bit block cipher E2, which was proposed to the AES (Advanced Encryption Standard) candidates. This algorithm supports 128-bit, 192-bit, and 256-bit secret keys. The design philosophy of E2 is highly conservative; the structure uses 12-round Feistel as its main function whose round function is constructed with 2-round SPN structure, and initial/final transformational functions. E2 has practical security against differential attack, linear attack, cryptanalysis with impossible differential, truncated differential attack, and so on. Furthermore, E2 can be implemented efficiently and flexibly on various platforms because the primitive operations involve byte length processing.
Yoshiki SAMESHIMA Hideaki SAISHO Kazuko OYANAGI Tsutomu MATSUMOTO
The authors present a multiparty signature generation (MSG) scheme of the Digital Signature Algorithm (FIPS 186-1). The scheme is based on a simple idea, however, it is much more convenient in usability in the real world than existing MSGs. The scheme has the following properties: (1) valid signatures are generated with odd n split private keys, (2) broadcast messages between the key holders are hidden from them, so that the n key holders do not need to process signature generation simultaneously, (3) even if up to t (= ) split keys are stolen, the adversary can get no information on the private key, (4) the scheme is as secure as the original signature algorithm against chosen message attack, and (5) the scheme is efficient in the sense that an implementation on smart card has demonstrated practical performance for interactive use with human user.
Masayuki KANDA Tsutomu MATSUMOTO
This paper studies security of Feistel ciphers with SPN round function against differential cryptanalysis, linear cryptanalysis, and truncated differential cryptanalysis from the "designer's standpoint." In estimating the security, we use the upper bounds of differential characteristic probability, linear characteristic probability and truncated differential probability, respectively. They are useful to design practically secure ciphers against these cryptanalyses. Firstly, we consider the minimum numbers of differential and linear active s-boxes. They provide the upper bounds of differential and linear characteristic probability, which show the security of ciphers constructed by s-boxes against differential and linear cryptanalysis. We clarify the (lower bounds of) minimum numbers of differential and linear active s-boxes in some consecutive rounds of the Feistel ciphers by using differential and linear branch numbers, Pd, Pl, respectively. Secondly, we discuss the following items on truncated differential probability from the designer's standpoint, and show how the following items affect the upper bound of truncated differential probability; (a) truncated differential probability of effective active-s-box, (b) XOR cancellation probability, and (c) effect of auxiliary functions. Finally, we revise Matsui's algorithm using the above discussion in order to evaluate the upper bound of truncated differential probability, since we consider the upper bound of truncated differential probability as well as that of differential and linear probability.
Tsutomu MATSUMOTO Youichi TAKASHIMA Hideki IMAI Minoru SASAKI Hiroharu YOSHIKAWA Shin-ichiro WATANABE
This paper demonstrates and confirms that a large-network-oriented key sharing method called the key predistribution system (KPS) is really practical and useful for supporting end-to-end cryptographic communication, by presenting a prototype implementation of KPS using special IC cards and its application to facsimile systems. This prototype can build a secure channel over any ordinary facsimile network using the following types of equipments: (1) an IC card implementing a linear scheme for KPS and the DES algorithm, (2) an adaptor-type interface device between the IC card and a facsimile terminal with no cryptographic function, and (3) a device for each managing center of KPS.
Tsutomu MATSUMOTO Makoto IKEDA Makoto NAGATA Yasuyoshi UEMURA
The Internet of Things (IoT) implicates an infrastructure that creates new value by connecting everything with communication networks, and its construction is rapidly progressing in anticipation of its great potential. Enhancing the security of IoT is an essential requirement for supporting IoT. For ensuring IoT security, it is desirable to create a situation that even a terminal component device with many restrictions in computing power and energy capacity can easily verify other devices and data and communicate securely by the use of public key cryptography. To concretely achieve the big goal of penetrating public key cryptographic technology to most IoT end devices, we elaborated the secure cryptographic unit (SCU) built in a low-end microcontroller chip. The SCU comprises a hardware cryptographic engine and a built-in access controlling functionality consisting of a software gate and hardware gate. This paper describes the outline of our SCU construction technology's research and development and prospects.
Satoshi OZAKI Tsutomu MATSUMOTO Hideki IMAI
The access control method adopted by UNIX is simple, understandable, and useful. However, it is quite possible that unexpected information flows occur when we are cooperating with some group members on UNIX. Introducing notions such as "flow right," "maximal permission" and "minimal umask value", this note proposes a simple method, can be seen as a natural extension of UNIX, to control indirect information flows without losing availability and understandability of UNIX.
Kyosuke YAMASHITA Ryu ISHII Yusuke SAKAI Tadanori TERUYA Takahiro MATSUDA Goichiro HANAOKA Kanta MATSUURA Tsutomu MATSUMOTO
A fault-tolerant aggregate signature (FT-AS) scheme is a variant of an aggregate signature scheme with the additional functionality to trace signers that create invalid signatures in case an aggregate signature is invalid. Several FT-AS schemes have been proposed so far, and some of them trace such rogue signers in multi-rounds, i.e., the setting where the signers repeatedly send their individual signatures. However, it has been overlooked that there exists a potential attack on the efficiency of bandwidth consumption in a multi-round FT-AS scheme. Since one of the merits of aggregate signature schemes is the efficiency of bandwidth consumption, such an attack might be critical for multi-round FT-AS schemes. In this paper, we propose a new multi-round FT-AS scheme that is tolerant of such an attack. We implement our scheme and experimentally show that it is more efficient than the existing multi-round FT-AS scheme if rogue signers randomly create invalid signatures with low probability, which for example captures spontaneous failures of devices in IoT systems.
Takayuki SASAKI Mami KAWAGUCHI Takuhiro KUMAGAI Katsunari YOSHIOKA Tsutomu MATSUMOTO
In recent years, cyber attacks against infrastructure have become more serious. Unfortunately, infrastructures with vulnerable remote management devices, which allow attackers to control the infrastructure, have been reported. Targeted attacks against infrastructure are conducted manually by human attackers rather than automated scripts. Here, open questions are how often the attacks against such infrastructure happen and what attackers do after intrusions. In this empirical study, we observe the accesses, including attacks and security investigation activities, using the customized infrastructure honeypot. The proposed honeypot comprises (1) a platform that easily deploys real devices as honeypots, (2) a mechanism to increase the number of fictional facilities by changing the displayed facility names on the WebUI for each honeypot instance, (3) an interaction mechanism with visitors to infer their purpose, and (4) tracking mechanisms to identify visitors for long-term activities. We implemented and deployed the honeypot for 31 months. Our honeypot observed critical operations, such as changing configurations of a remote management device. We also observed long-term access to WebUI and Telnet service of the honeypot.
Yuliang ZHENG Tsutomu MATSUMOTO Hideki IMAI
This paper proves several theorems on probabilistic cryptosystems. From these theorems it follows directly that a probabilistic cryptosystem proposed by the authors, whose security is based upon the (supposed) infeasibility of γth-Residuosity Problem, is polynomially secure. Techniques developed in the paper are of independent interest.
In 1980, Hellman presented "time-memory trade-off cryptanalysis" for block ciphers, which requires precomputation equivalent to time complexity of exhaustive search, but can drastically reduce both time complexity on intercepted ciphertexts of exhaustive search and space complexity of table lookup. This paper extends his cryptanalysis and optimizes a relation among the breaking cost, time, and success probability. The power of the optimized cryptanalytic method can be demonstrated by the estimates as of January 1995 in the following. For breaking DES in one hour with success probability of 50% or more, the estimated cost of a simple and a highly parallel machine is respectively about 0.26[million dollars] and 0.06[million dollars]. Also it takes about six and two years respectively until each machine costs for breaking FEAL-32 on the same condition decreases to 1[million dollars]. Moreover, it takes about 22.5 and 19[years] respectively until each costs for breaking Skipjack similarly decreases to 1[million dollars], but time complexity of precomputation is huge in case of the former. The cost-time product for this precomputation will decrease to 20[million dollars
Sachiko YOSHIHAMA Takaaki TATEISHI Naoshi TABUCHI Tsutomu MATSUMOTO
The emergence of Web 2.0 technologies such as Ajax and Mashup has revealed the weakness of the same-origin policy [1], the current de facto standard for the Web browser security model. We propose a new browser security model to allow fine-grained access control in the client-side Web applications for secure mashup and user-generated contents. We propose a browser security model that is based on information-flow-based access control (IBAC) to overcome the dynamic nature of the client-side Web applications and to accurately determine the privilege of scripts in the event-driven programming model.
Manuel CERECEDO Tsutomu MATSUMOTO Hideki IMAI
In this paper, we discuss secure protocols for shared computation of algorithms associated with digital signature schemes based on discrete logarithms. Generic solutions to the problem of cooperatively computing arbitraty functions, though formally provable according to strict security notions, are inefficient in terms of communication--bits and rounds of interaction--; practical protocols for shared computation of particular functions, on the other hand, are often shown secure according to weaker notions of security. We propose efficient secure protocols to share the generation of keys and signatures in the digital signature schemes introduced by Schnorr (1989) and ElGamal (1985). The protocols are built on a protocol for non-interactive verifiable secret sharing (Feldman, 1987) and a novel construction for non-interactively multiplying secretly shared values. Together with the non-interactive protocols for shared generation of RSA signatures introduced by Desmedt and Frankel (1991), the results presented here show that practical signature schemes can be efficiently shared.
Kunihiko MIYAZAKI Mitsuru IWAMURA Tsutomu MATSUMOTO Ryoichi SASAKI Hiroshi YOSHIURA Satoru TEZUKA Hideki IMAI
A digital signature does not allow any alteration of the document to which it is attached. Appropriate alteration of some signed documents, however, should be allowed because there are security requirements other than that for the integrity of the document. In the disclosure of official information, for example, sensitive information such as personal information or national secrets is masked when an official document is sanitized so that its nonsensitive information can be disclosed when it is demanded by a citizen. If this disclosure is done digitally by using the current digital signature schemes, the citizen cannot verify the disclosed information correctly because the information has been altered to prevent the leakage of sensitive information. That is, with current digital signature schemes, the confidentiality of official information is incompatible with the integrity of that information. This is called the digital document sanitizing problem, and some solutions such as digital document sanitizing schemes and content extraction signatures have been proposed. In this paper, we point out that the conventional digital signature schemes are vulnerable to additional sanitizing attack and show how this vulnerability can be eliminated by using a new digitally signed document sanitizing scheme with disclosure condition control.
Takenobu SEITO Yuki HARA Junji SHIKATA Tsutomu MATSUMOTO
A group signature scheme introduced by Chaum and Van Heyst allows a group member to sign messages anonymously on behalf of the group. However, in the case of a dispute, the identity of a signer of a group signature can be revealed only by a privileged entity, called a group manager. The group signature scheme has mainly been studied from the viewpoint of computational security setting so far. The main contribution of this paper is to study group signature schemes in unconditional security. More specifically, we newly introduce strong security notions of unconditionally secure group signatures (USGS for short) based on the idea of those of computationally secure group signatures proposed by Bellare, Micciancio and Warinschi. We also provide a generic method to construct USGS that is provably secure in our security definition. More precisely, we construct USGS by combining an encryption scheme with a signature, and show that the constructed scheme is unconditionally secure if the encryption and the signature used in the construction are unconditionally secure. Finally, we provide an instantiation of the one-time secure group signature scheme based on the generic construction.
Chaosheng SHU Tsutomu MATSUMOTO Hideki IMAI
In this paper, we propose a multi-purpose proof system which enables a user remembering only one piece of secret data to perform various proof protocols. These proofs include identity proof, membership proof without disclosing identity, and combined identity and membership proof. When a user participates in a group, he will obtain a secret witness from the group administrator. Many secret witnesses can be combined into one piece of secret data. But the size of the secret data is independent of the number of the groups in which the user participates. Our system satisfies other desirable properties which were not attained by the previously proposed systems.
Yasuyoshi KANEKO Tsutomu MATSUMOTO
This letter examines outline measures of strength against the differential and linear cryptanalysis. These measures are useful to estimate the number of rounds giving an immune iterated cipher. This letter reports that the outline measures of strength are useful to relatively estimate the strength of generalized feistel ciphers.
Ryu ISHII Kyosuke YAMASHITA Zihao SONG Yusuke SAKAI Tadanori TERUYA Takahiro MATSUDA Goichiro HANAOKA Kanta MATSUURA Tsutomu MATSUMOTO
Fault-tolerant aggregate signature (FT-AS) is a special type of aggregate signature that is equipped with the functionality for tracing signers who generated invalid signatures in the case an aggregate signature is detected as invalid. In existing FT-AS schemes (whose tracing functionality requires multi-rounds), a verifier needs to send a feedback to an aggregator for efficiently tracing the invalid signer(s). However, in practice, if this feedback is not responded to the aggregator in a sufficiently fast and timely manner, the tracing process will fail. Therefore, it is important to estimate whether this feedback can be responded and received in time on a real system. In this work, we measure the total processing time required for the feedback by implementing an existing FT-AS scheme, and evaluate whether the scheme works without problems in real systems. Our experimental results show that the time required for the feedback is 605.3 ms for a typical parameter setting, which indicates that if the acceptable feedback time is significantly larger than a few hundred ms, the existing FT-AS scheme would effectively work in such systems. However, there are situations where such feedback time is not acceptable, in which case the existing FT-AS scheme cannot be used. Therefore, we further propose a novel FT-AS scheme that does not require any feedback. We also implement our new scheme and show that a feedback in this scheme is completely eliminated but the size of its aggregate signature (affecting the communication cost from the aggregator to the verifier) is 144.9 times larger than that of the existing FT-AS scheme (with feedbacks) for a typical parameter setting, and thus has a trade-off between the feedback waiting time and the communication cost from the verifier to the aggregator with the existing FT-AS scheme.
Hiroki NAKANO Daiki CHIBA Takashi KOIDE Naoki FUKUSHI Takeshi YAGI Takeo HARIU Katsunari YOSHIOKA Tsutomu MATSUMOTO
The increase in phishing attacks through email and short message service (SMS) has shown no signs of deceleration. The first thing we need to do to combat the ever-increasing number of phishing attacks is to collect and characterize more phishing cases that reach end users. Without understanding these characteristics, anti-phishing countermeasures cannot evolve. In this study, we propose an approach using Twitter as a new observation point to immediately collect and characterize phishing cases via e-mail and SMS that evade countermeasures and reach users. Specifically, we propose CrowdCanary, a system capable of structurally and accurately extracting phishing information (e.g., URLs and domains) from tweets about phishing by users who have actually discovered or encountered it. In our three months of live operation, CrowdCanary identified 35,432 phishing URLs out of 38,935 phishing reports. We confirmed that 31,960 (90.2%) of these phishing URLs were later detected by the anti-virus engine, demonstrating that CrowdCanary is superior to existing systems in both accuracy and volume of threat extraction. We also analyzed users who shared phishing threats by utilizing the extracted phishing URLs and categorized them into two distinct groups - namely, experts and non-experts. As a result, we found that CrowdCanary could collect information that is specifically included in non-expert reports, such as information shared only by the company brand name in the tweet, information about phishing attacks that we find only in the image of the tweet, and information about the landing page before the redirect. Furthermore, we conducted a detailed analysis of the collected information on phishing sites and discovered that certain biases exist in the domain names and hosting servers of phishing sites, revealing new characteristics useful for unknown phishing site detection.